1. Field of the Invention
The present invention relates to a method and apparatus for detecting range images indicative of the shape of objects in a visual scene. More specifically, the present invention is related to a combination of a triangulation-based image formation arrangement and electronic circuit which senses and process radiation received thereon, thereby enabling a rapid, accurate and high resolution collection of range data.
2. Description of the Prior Art
High-speed gathering of high-accuracy 3D information of visual scenes is important in many applications. As employed herein xe2x80x9cvisual scenesxe2x80x9d orxe2x80x9cscenesxe2x80x9d means visible surfaces of objects in the environment falling within a range sensor""s field of view. In computer-aided design (CAD) and computer graphics, for example, it is useful to digitize the 3D shape of these objects as a starting description of solid shapes as to ease and enable further manipulation and analysis of these shapes by the computer. Similarly, in industrial applications, such as object inspection, it is useful to acquire shape of industrial parts and analyze them by a computer. Since robots, as humans, can greatly benefit from the knowledge of 3D information about their environment, range images are extremely useful for robotics. Robotic applications benefiting from range images include automated assembly, obstacle detection, navigation and motion planing, among others.
The importance and usefulness of obtaining range images have been known by those skilled in the art. In a paper entitled, Range Imaging Sensors, published by General Motors Research Labs., Warren, Mich., Research Publication GMR-6090, March 1988, P. J. Besi describes various range imaging sensors. The paper concludes that triangulation-based light stripe methods are the most practical and quite robust in many applications.
As well known to many skilled in the art, a conventional triangulation range imaging method projects a slit ray of light onto a scene. A sensor array, usually a CCD camera, images the scene from an oblique angle. In such arrangement, the intersection of the surface of the object and the slit ray produces a contour in the image indicative of the local object shape. In order to ease the detection of the slit ray in the image, the illumination conditions are usually adjusted so that the projected slit ray generates a prominently bright features in the scene.
Conventional triangulation methods collect range maps one slice at a time. The slit ray illuminating a scene is fixed at a particular position. The scene is projected onto an image plane through a system of lenses. Ordinarily the scene is imaged with a one- or two-dimensional array of photodetectors, such as a CCD image sensor, whose row or rows are substantially perpendicular to the axis of rotation of the slit ray. The sensed image is collected and each row examined by a computer to find the location of the light ray projection in each row. Using this location and the geometric parameters of the triangulation imaging arrangement, the range or distance to the point on the object can be computed.
By continuing this process for each row, one slice of range image is obtained. Then, the laser stripe is repositioned and another slice of the range image is collected. One problem with this known process is that it is too slow as each slice requires at least one camera frame time.
High-speed triangulation approaches have been proposed in prior art in which the slit ray continuously sweeps across the scene. This approach is sometimes called xe2x80x9cdynamic triangulationxe2x80x9d.
U.S. Pat. No. 4,794,262 to Y. Sato et al. discloses a triangulation setup with a continuously sweeping slit ray across the scene. The scene is viewed with the array of mutually independent photosensors. Each photosensor in the array has its own line of sight and xe2x80x9cseesxe2x80x9d the slit ray only once as it sweeps by, assuming there are no interreflections among surfaces in the scene. The time t when a particular detector at a particular location sees the laser is recorded. Then using a computer, the position that the slit ray assumed at the instant t is determined. Again, using the location of the particular detector together with the geometric parameters of the slit ray and the triangulation setup, the range along the line of site for the particular detector is computed. In this disclosure, the time is recorded in a memory array whose cells have one-to-one correspondence to the detector array cells.
U.S. Pat. No. 5,107,103 to Gruss et al. discloses a very-large-scale-integration (VLSI) chip method. Each cell in the sensor array has a photodiode, a comparator for thresholding the sensory signal to detect when the slit ray shines across the photosensor and an analog memory for storing the timestamp in each cell. By hard-wiring a memory cell in each cell this method also records time in a memory array whose tells have one-to-one correspondence to the detector array cells. One deficiency of this method is the fact that the thresholding is not a reliable method for detecting the passage of the slit ray. The sensory signal may be unable to reach the preset threshold due to varying reflectivity of the object and circuitry temperature drifts. Therefore, the passage of the projection of the slit ray across a cell may remain undetected.
U.S. Pat. No. 5,408,324 to K. Sato et al. shows another VLSI implementation is of the same method whereas each cell in the sensor array includes two photosensors disposed side by side in the direction of the slit ray sweep. By comparing the photocurrents, the passage of the image of the slit ray is detected when the appreciable difference between the photocurrents is observed. Yokoyama et al. U.S. Pat. No. 5,436,727 discloses that such a detection of the slit ray passage is more robust to varying object reflectance and temperature variations, and remedies one deficiency of the implementation by Gruss et al. This approach can produce a new problem. While the pair of photosensors is waiting to xe2x80x9cseexe2x80x9d the image of the slit ray, their sensory signals are of similar intensities, thus making it difficult for the comparator in each cell to determine which signal is greater. In fact, due to the noise and the limited resolution of the comparator, the comparator""s output is very likely to transition erratically before the image of the slit ray actually passes cross the photosensors. A more recent patent by the same group of inventors, U.S. Pat. No. 5,847,833 to Yokoyama et al., introduces a hysteresis to the comparison process. The area of one of the two photosensors is sized a few percent larger than the area of the other. The smaller photosensor is the one that is to receive the image of the slit ray first, while the larger photosensor receives it second. The object is to prevent faulty and premature transitions of the comparator""s output. Due to the ambient illumination and the reflectivity patterns of the scene, however, one might have such a light distribution over the two photosensors that could nullify the hysteresis produced by different area size, thus still causing unreliable performance. This disclosure also records time in a memory array whose cells have one-to-one correspondence to the detector array cells.
Several deficiencies of the above-described prior art have already been mentioned. The main deficiency of these three methods stems from the fact that they are cell-parallel. That is, the range sensor is an array of mutually independent cells that are able to detect the slit ray as it sweeps across the scene and record the time when it is detected. These approaches, therefore, require one-to-one correspondence between the memory array cells and the detector array cells. This deficiency of these methods is manifested in at least two ways. Large cell size is required if the memory is located in the cell together with the slit ray detector (see U.S. Pat. No. 5,107,103 to Gruss et al.). The large cell size limits the spatial resolution of the range sensor. If the memory cell is not located in the close electrical proximity to the detector, a cumbersome readout and communication implementation is required to associate the detector array with the memory array SO as to ensure recording of the timestamp in a timely and accurate manner. See U.S. Pat. No. 4,794,262 to Y. Sato, U.S. Pat. No. 5,408,324 to K. Sato et al. U.S. Pat. No. 5,436,727 to Yokoyama and U.S. Pat. No. 5,847,833 to Yokoyama. Such cumbersome readout introduces latency that degrades accuracy of stored timing information, and consequently degrades the accuracy of the range measurement.
The main deficiency of these cell-parallel techniques can be avoided by noting that the triangulation ranging technique is inherently row-parallel. Assuming there are no significant multiple reflections among surfaces in the scene, there is only one location in each row that xe2x80x9cseesxe2x80x9d the image of the slit ray at any given time. As a result, the detection of the image of the slit ray is a global operation over plurality of photosensors in each row. In the row-parallel approach, the task is to detect repeatedly locations of the slit ray image as it sweeps across the row and associate those locations with times when the detection occurred. If memory is needed, the row-parallel approach requires only one memory per row for storing timestamps, thus enabling smaller cells and higher spatial resolution.
A Master Thesis by Kuo entitled, xe2x80x9cA VLSI System for Light-Stripe Range Imagingxe2x80x9d, submitted to the Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, Pa. (1992) shows a row-parallel sensor with the dynamically swept slit ray. Kuo shows a single one-dimensional (1D) array of photosensors and a distributed analog winner-take-all (WTA) circuit. As known to those skilled in the art, a WTA is a global processor that takes a plurality of inputs and identifies one input that has the largest magnitude. In addition, the WTA used by Kuo continuously reports the intensity of the winning input.
The underlying assumption in Kuo""s work is that under favorable imaging conditions the slit ray image is the strongest optical feature in the row causing the WTA to identify the location of that feature. Furthermore, as the projection of the slit ray passes across the winning photosensor, the magnitude of the winning input continuously reported by the WTA will first rise, then peak and finally decay. The peak is observed when the image of the slit ray is substantially centered on the photosensor. Therefore, by detecting a timing of this peak, Kuo is able to determine timing when the sweeping image of the slit ray is substantially centered on the photodetector of the cell identified by the WTA as the winner. To locate the winning cell, Kuo rapidly scans and polls each cell of the WTA to determine which one is winning. Only one peak detector and one memory cell for storing timestamps is required per row, provided that the memory is read out before it is needed for the next timestamp storage.
Kuo""s thesis partially remedies the problem of large cell size of the prior art such as Gruss et al. U.S. Pat. No. 5,107,103 and remedies the problem of cumbersome readout apparent in the other two prior art embodiments described earlier. However, several deficiencies remain. One deficiency is that to obtain a well-pronounced temporal peak the photosensor needs to be large enough to collect enough photons as the slit ray image passes over it. As a result, the detector size still limits the spatial resolution of the sensor. While in many industrial applications the image formation arrangement can be controlled so that the slit ray produce the brightest features in the scene, other important applications remain in which it cannot be done. Therefore, the main deficiency of Kuo""s range finder is the requirement that the slit ray produces the brightest feature in the scene. Another deficiency of Kuo""s device is the electronic scanning of the WTA for determining which input is winning. Such scanning does not extend well into two-dimensional sensors.
Despite these prior art systems, there remains a very real and substantial need for a method and apparatus for rapid, accurate and high resolution range imaging by overcoming disadvantages and limitations of the prior art.
The above-described need has been met by the present invention.
The method of the present invention provides for range imaging of a scene by directing a planar light beam onto a first portion of the scene and delivering a reflected light stripe from the first portion to a row of sensors. The sensors emit responsive electrical signals which are processed by creation of a salient feature containing saliency map with the salient feature being spatially related to the reflected light stripe and not being based on the instantaneous light impinging on a single sensor. Continued sweeping of the light progressively establishes salient feature information for a plurality of scene portions which information by means of an appropriate processor, such as a computer, is converted into the range image. The information obtained from the sensor output may be processed by a preprocessor array to convert it into a saliency map after which, in a preferred embodiment, a winner-take-all processor selects the salient feature which may, for example, be a peak or valley from a particular stripe as determined by a linear sensor array.
The information regarding position may be combined with time or angle information to establish a segment of the scene image with repetition of the process creating the entire image.
The apparatus of the present invention contemplates a triangulation arrangement wherein a light source provides a planar light beam which impinges upon a portion of the scene which may be a three-dimensional physical object and has a reflected light stripe directed toward a linear sensor array or two parallel sensor arrays with a salient feature of the light impinging on the sensor array being determined as by a winner-take-all circuit. This information is delivered to a processor along with information with respect to time and angle and an image unit is generated. Repeating this cycle through sweeping of the light beam to different portions of the scene or object sequentially produces the scene image.
It is an object of the present invention to provide a method and apparatus for rapid range imaging which enables high spatial resolution sensing.
It is a further object of the present invention to provide such a system which provides rapid high resolution range images of scenes.
It is a further object of the present invention to provide such a system wherein the amount of circuitry in each cell is reduced.
It is yet another object of the present invention to provide such a system which provides for efficient on-chip processing through the use of winner-take-all circuitry on the chip.
These and other objects of the invention will be more fully understood from the following description of the invention on reference to the illustrations appended hereto.